nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3
nums = [1], k = 1

// var maxSlidingWindow = function (nums, k) {
//     let result = []
//     let queue = []
//     let len = nums.length
//     queue.push(0)
//     if (len === 1) return [nums[0]]

//     for (let i = 1; i < len; i++) {
//         while (queue.length && nums[i] > nums[queue[queue.length - 1]]) {
//             queue.pop()
//         }
//         queue.push(i)

//         while (queue.length && i - queue[0] >= k) {
//             queue.shift()
//         }

//         if (i >= k - 1) {
//             result.push(nums[queue[0]])
//         }
//     }
//     return result
// }

var maxSlidingWindow = function (nums, k) {
    // 思路：维护一个长度为k的单调递减队列，遍历原数组，当遍历到的下标超过k时读取队列头部元素，当队列头部的元素和当前读到的下标长度大于k时，移除队列头部元素
    let res = [];
    let deque = [];

    for (let i = 0; i < nums.length; i++) {
        while (deque.length && nums[deque[deque.length - 1]] < nums[i]) {
            deque.pop();
        }
        deque.push(i);
        while (deque.length && deque[0] <= i - k) {
            deque.shift()
        }
        if (i - k >= -1) {
            res.push(nums[deque[0]])
        }
    }
    return res
}

console.log(maxSlidingWindow(nums, k));
